什麼是堆疊？

堆疊（Stack）：是指一個具有後進先出（Last-In First-Out, LIFO）特性的有序串列。
也就是說，加入和刪除元素發生在頂端（top），加入的動作稱為 push，刪除的動作稱為 pop。

一個堆疊類別提供的操作

堆疊類別可以提供給使用者以下幾種的動作：

1. create(S)：創建一個堆疊 S
2. isEmpty(S)：判斷堆疊 S 是否為空
3. isFull(S)：判斷堆疊 S 是否為滿
4. push(S, item)：加入元素 item 進入堆疊
5. pop(S)：刪除堆疊頂端的元素

堆疊的實作（Implementation）

這邊就是堆疊的第一個大重點啦，主要會集中在 push 和 pop 的實作上，主要有兩種實作方式

1. Array：https://www.geeksforgeeks.org/array-data-structure-guide/
2. Linked List：https://www.geeksforgeeks.org/linked-list-data-structure/

這兩個資料結構很基本，基本上所有進階的資料結構都是由 Array 和 Linked List 實作出來的。
這邊放上參考的連結，大家可以先去看看這兩個資料結構喔。

使用 Array 實作 Stack

0. 前情提要：如果用 Array 製作堆疊，那麼有兩個資料需要先宣告：一個 Array，及一個整數變數 top 代表目前頂端元素在哪個 Index，預設值為 -1。
1. Create：使用 Array 的最大問題是，必須事先宣告陣列的大小，也就是說，堆疊有可能會滿。
2. IsEmpty、IsFull：這兩個一起說，如果 top = -1，代表目前堆疊中沒有任何的元素，也就是堆疊為空；如果top = 陣列長度 - 1 則代表目前陣列所有的空間都有元素，就代表堆疊滿了。
   至於為甚麼是陣列長度 - 1，因為陣列的開頭是從 0 開始的！
3. push：如果陣列是滿，則不能再新增元素進入堆疊，如果未滿，則：
   先將 top 值加一後，將資料放入該 Index。
   流程圖：
   
4. pop：如果陣列為空，則不能刪除資料，如果非空，則：
   先將 top 該位置的元素取出，用一個變數存，再將top 值 - 1，最後回傳存元素的變數值。
   流程圖：
   至於為何不需要將 item 從陣列中刪除，是因為到時候若有新資料 push 進入堆疊，就會直接覆蓋掉了，所以不需要清除資料！

使用 Linked List 實作 Stack

0. 前情提要：使用鏈結串列製作堆疊的話，首先要定義 Node Structure:

另外：top也是一個指標（pointer），預設值為 NULL(空值)，top 指向的節點就是頂端元素。

1. Create: 設定 top 指標為 NULL。
2. IsFull：因為是鏈結串列，且節點是 dynamic allocate 出來的，因此，除非你將系統配置給你的空間全部用完，否則 Stack 不會滿，可以一直 push 元素。因此我們不實作這個 method。
3. IsEmpty：如果 top 指向 NULL，代表堆疊為空
4. push：先動態配置一個節點空間，並將資料放入節點之 Data 欄位，並將 link 欄位指向目前堆疊頂端之元素，最後將 top 指標指向新節點。
   流程圖：
   
5. pop：先判斷堆疊是否為空，若非空：則
   使用一個新的指標（P）指向堆疊頂端元素（為了等等更改 top 指標後該節點仍能存取），並將該節點之資料取出。接著將 top 指標指向堆疊內下一個元素，最後釋放 P 之節點空間並 Return 資料。
   流程圖：
   

實作程式碼

細講了每個操作的流程，也畫了流程圖，該把她轉換成程式碼了，用 C++ 來實作堆疊類別：

Array 實作：

#include <iostream>
#include <limits.h>
#define SIZE 256
using namespace std;

class Stack{
    private:
        int* arr;
        int top;
    public:
        Stack();
        bool isEmpty();
        bool isFull();
        void push(int item);
        int pop();
};

Stack::Stack(){
    this->arr = new int[SIZE];
    this->top = -1;
}
bool Stack::isEmpty(){
    if(this->top <= -1) return true;
    else return false;
}
bool Stack::isFull(){
    if(this->top >= SIZE - 1) return true;
    else return false;
}
void Stack::push(int item){
    if(isFull()){
        cout << "push fail" << endl;
    }else{
        this->top++;
        arr[top] = item;
    }
}
int Stack::pop(){
    if(isEmpty()){
        cout << "pop fail" << endl;
        return INT_MIN;
    }else{
        int x = arr[this->top];
        this->top--;
        return x;
    }
}

Linked List 實作：

#include <iostream>
#include <limits.h>
using namespace std;

typedef struct node{
    int data;
    struct node* link;
}node_t;

class Stack{
    private:
        node_t* top;
    public:
        Stack();
        bool isEmpty();
        void push(int item);
        int pop();
};

Stack::Stack(){
    this->top = nullptr;
}
bool Stack::isEmpty(){
    if(this->top == nullptr) return true;
    else return false;
}
void Stack::push(int item){
    node_t* newNode = new node_t;
    newNode->data = item;
    newNode->link = this->top;
    this->top = newNode;
}
int Stack::pop(){
    if(isEmpty()){
        cout << "pop fail" << endl;
        return INT_MIN;
    }else{
        node_t* p = this->top;
        int x = p->data;
        this->top = p->link;
        delete p;
        return x;
    }
}